﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ShortestPaths.General
{

    public class PreBellmanFordShortestPathsesFinder<T> : IShortestPathsFinder<T,double>
    {
        private readonly Func<IEnumerable<T>, IMap<T, double>> _createDistancesMap;
        private readonly Func<IEnumerable<T>, IMap<T, T>> _createBackpointersMap;

        public PreBellmanFordShortestPathsesFinder(Func<IEnumerable<T>,IMap<T,double>> createDistancesMap = null,
                                                   Func<IEnumerable<T>,IMap<T,T>> createBackpointersMap = null)
        {
            _createDistancesMap = createDistancesMap ?? (it => AlgoritmiaFactory.Maps<T, double>.Default);
            _createBackpointersMap = createBackpointersMap ?? (it => AlgoritmiaFactory.Maps<T, T>.Default);
        }

        #region Implementation of IShortestPathFinder<T,double>

        public IEnumerable<KeyValuePair<T, T>> SomeToSomeBackpointers(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var distances = _createDistancesMap(g.V);
            var backpointers = _createBackpointersMap(g.V);
            foreach(var v in g.V)
            {
                distances[v] = double.PositiveInfinity;
                backpointers[v] = v;
            }
            foreach(var s in sources)
            {
                distances[s] = 0.0;
            }

            for(int i = 0; i < g.V.Count-1; i++)
            {
                foreach(var v in g.V)
                {
                    var preds = g.Predecessors(v).ToList();
                    if ( preds.Count > 0)
                    {
                        var u = preds.ArgMin(p => distances[p] + d(p, v));
                        if ( distances[u] + d(u,v) < distances[v])
                        {
                            distances[v] = distances[u] + d(u, v);
                            backpointers[v] = u;
                        }
                    }
                }
            }
            return backpointers;
        }

        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var distances = _createDistancesMap(g.V);
            foreach(var v in g.V)
            {
                distances[v] = double.PositiveInfinity;
            }
            foreach(var s in sources)
            {
                distances[s] = 0.0;
            }
            for(int i = 0; i < g.V.Count -1; i++)
            {
                foreach(var v in g.V)
                {
                    distances[v] = Math.Min(distances[v], (from p in g.Predecessors(v)
                                                          select distances[p] + d(p, v)).DefaultIfEmpty(double.PositiveInfinity).Min());
                }
            }

            return (from t in targets
                   select distances[t]).Min();
        }

        #endregion
    }
}
